Khi học lớp 5, Yudhoyono được tham quan Học viện Quân đội Quốc gia AMN tại Magelang. Sau khi quan sát việc huấn luyện sĩ quan và được truyền cảm hứng từ nghề nghiệp của người cha, Yudhoyono quyết định tham gia học tại Học viện này để trở thành quân nhân. Nhưng việc tham gia học tại Học viện đã không thành.

Từ năm 1971 đến năm 1973, học tại Học viện Quân sự Indonesia AKARI. Yudhoyono tốt nghiệp hạng ưu tú nhất của Học viện này, và được Tổng thống Suharto tặng thưởng Huân chương Adhi Makayasa. Sau khi tốt nghiệp, Yudhoyono tham gia quân dự bị chiến lược (Kostrad), trở thành Trung đội trưởng Tiểu đoàn không quân. Ngoài việc lãnh đạo đội quân này, Yudhoyono còn được giao nhiệm vụ giảng dạy kiến thức tổng quát và tiếng Anh cho tiểu đoàn. Năm 1975, Yudhoyono tham gia khóa huấn luyện không quân và kỵ binh tại Căn cứ Benning, Hoa Kỳ.

Năm 1976, Yudhoyono đảm nhiệm chức Trung đội trưởng Tiểu đoàn 305 đóng tại Đông Timor; cũng giống như các sĩ quan khác của Indonesia đóng tại Đông Timor, ông cũng bị cáo buộc về những tội ác chiến tranh. Năm 1977, Yudhoyono trở thành Trung đội trưởng súng cối; năm 1977 đến 1978, Sĩ quan phụ trách hành quân của Lữ đoàn không quân; năm 1979 - 1981, Tiểu đoàn trưởng tại Kostrad; năm 1981 - 1982, làm việc tại Sở Chỉ huy Quân sự.

Năm 1995 - 1996, Yudhoyono được cử làm Chỉ huy trưởng Lực lượng Quân đội Indonesia tham gia Lực lượng gìn giữ hòa bình của Liên hiệp quốc tại Bosnia.

Yudhoyono kết thúc sự nghiệp của mình trong Quân đội Indonesia với cấp bậc Trung tướng.